package com.lihepeng.leecode.recursive;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 *
 * 你可以按 任何顺序 返回答案。
 */
public class Solution77 {
    /**
     * 使用回溯完成 跳出条件 当数量等于
     * @param n
     * @param k
     * @return
     */
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        recursive(n,k,1,new LinkedList<>());
        return result;
    }
    private void recursive(int n,int k,int start,Deque<Integer> item){
        if (item.size() == k) {
            result.add(new ArrayList<>(item));
            return;
        }
        for (int i=start;i<=n;i++) {
            item.addLast(i);
            recursive(n,k,i+1,item);
            item.removeLast();
        }

    }
}
